This invention relates generally to computer systems and more specifically to a method for testing integrated circuits.
As it is known in the art, a computer system is generally comprised of a central processing unit, a memory system, a cache system, an IO system, and a system bus for connecting each. The central processing unit is generally comprised of a program counter, a memory management unit for reading and writing memory, control logic for fetching instructions from memory, and an execution box for executing instructions which includes an arithmetic logic unit and high speed memory locations referred to as registers.
When system engineers design a computer system, they perform functional and timing parameter calculations to ensure that all elements of the system will operate correctly by meeting the requirements of each element which it interfaces with. For example, if a central processing unit is going to interface with an attached memory system it has to have a sufficient number of address lines for accessing all parts of the memory. Further, the address lines have to be connected to the appropriate places in the memory system and the timing, which governs when the address is presented to the associated memory has to agree with the input-output timing of the memory system.
In a computer system, a central processing unit's foremost job is to fetch an instruction from memory and to execute the specified operation. Computer programs are groups of these instructions constructed in a sequenced order to guide the computer system in performing a task. A central processing unit executing a program fetches an instruction from memory, stores the location of the next instruction in the sequence, manipulates the data as instructed, stores the result, and fetches the next instruction.
The basic types of CPU instructions are generally comprised of control flow instructions, data read instructions, data write instructions, data compare instructions, logical operation instructions, and null instructions. The control flow instructions are comprised of conditional and unconditional branching operations which cause program execution to jump to different sequences of instructions based on the occurrence of a specified system event or a data value. These are important instructions because they guide the CPU in executing the correct sequence of read, write, and compare instructions to properly accomplish the desired task.
In order to verify that the timing and functionality of each element in a computer system will work properly, system engineers produce a computer model of the design. Each element in the system has a unique model which represents the operation of its input and output signals in response to stimulus from other elements which interface with it. Generally the models representing the central processing unit are the most complex. These CPU models have to be sophisticated enough to fetch, and respond properly to, programs of instructions stored in simulated memory elements.
In order to sufficiently test these circuits the simulation programs have to exercise the model as extensively as possible. In order to do this, a method of simulating integrated circuits with randomly generated test cases is employed. This type of testing presents simulated inputs to a model of an integrated circuit and monitors the resulting state of the device. In this manner a design engineer can verify that an integrated circuit meets its functional requirements before receiving actual hardware. The testing process can be as complex as functionally providing the device with simulated memory, clocks, and registers necessary for proper operation and then testing the device by providing a simulated stream of machine code instructions. A test would include monitoring all system attributes such as address, data, interrupts, cache operations, the value of registers and flags, and bus contention. This scenario usually involves the simulation of complex CPU circuitry.
One technique known in the art was to manually design a set of test cases by hand to control the functional simulation of the chip's circuits. Each pass of instructions would attempt to test a specific function of the design's operation and were designed to bring about marginal functional and timing conditions which could cause a device to fail.
One problem with this technique is that manual generation of test cases is a tedious process made even more difficult by the ever growing complexity of circuits to be tested. One of the main problems was that test case generation was time consuming. For each mode of operation an engineer had to generate many test cases which he or she believed would bring about a marginal functional or timing condition. This process was inefficient because the coverage of the tests depended entirely on the number of test cases that the engineer could foresee. Many problem areas could be overlooked because the engineer could not conceive of the results of a complex test case or the interaction between different test cases. A further problem is that each engineer has his or her own style of writing test cases which could lead to oversight of certain failing conditions.
Because of these many problems, automated test case generating methods were developed. A design engineer would input the "rules" of the test, for example the instructions for a central processing unit, and then these systems randomly generated groups of test cases. These systems offered the benefits of reduced generation time and produced tests which exercised the device in a manner which was closer to actual operation. The engineer could still tailor any specific test, but the test generator could use that test in random combination with other tests to increasing its effectiveness.
A benefit of these systems was the generation of random branching and jumping tests through the use of control flow instructions. Control flow instructions allow programs to jump to different sections of code depending on the happening of specified conditions. Today this has the advantage of testing the jump or branch prediction algorithms that are built into many CPUs. These algorithms attempt to predict whether a jump or branch instruction will execute before actually evaluating the condition that will cause the jump or branch to happen. The CPU will begin acting on this prediction, for example gaining access to a particular location in memory, in order to speed up the overall transaction. Because these algorithms are so crucial to the speed of a computer system it is vital that they are highly stressed during simulation.
Random generation of test cases however, leads to the problem of developing infinite looping tests. An infinite loop is constructed where the test code jumps to an instruction block whose operation causes a jump back to the block that originally jumped to it. Once in this loop the test program will remain until it is stopped by the engineer or until the system runs out of memory. The problem with this is that it prevents the execution of any test instruction that comes afterwards and yields no further useful information.
Prior art systems attempted to get around the problem of infinite loops by allowing test case generators to branch only in the forward direction. This means that a program counter is continually incremented until the end of the program is reached. This method prevents infinite loops in the test process however it also excludes cases comprised of complex jumping and branching operations which might be encountered during actual operation of the hardware. Moreover the use of backward branching, which is highly beneficial to the test process since it allows controlled loops to be implemented, is also restricted. Controlled loops are produced by allowing the program counter to be reset to the instruction at the beginning of the loop. They are used to cause overflow conditions in buffers, to cause assertion of interrupts, to test special looping instructions available in most CPU designs, to wait for certain conditions to occur, and many other useful testing functions. This solution therefore severely limits the effectiveness of randomly generated simulation test cases.